/* 

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

说明：不允许修改给定的链表。

进阶：

你是否可以使用 O(1) 空间解决此题？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/linked-list-cycle-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

*/

/* 

结论：现在的解法就很清晰了，当快慢指针相遇之后，让新指针从头出发，和慢指针同时前进，且每次前进一步，两者相遇的地方，就是环起点。

*/

var detectCycle = function (head) {
    if (head === null || head.next === null)
        return null; // 这里返回的是 null 而不是 head

    // 这里不能使用dummyHead并且使得slow&fast = dummyHead
    // 因为这样设置会使得第一次相遇的点不是尾部连接到链表中的点
    // 会导致超时的原因是再也没有第二次相遇了
    let slow = fast = head;
    let isCycle = false;

    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow === fast) {
            isCycle = true;
            break;
        }
    }

    if (!isCycle) {
        return null;
    }

    fast = head;

    while (fast != slow) {
        slow = slow.next;
        fast = fast.next;
    }

    return slow;
}